package main

type Stack struct {
	container []interface{}
	top       int
	size      int
}

func NewStack(size int) *Stack {
	return &Stack{
		container: make([]interface{}, size),
		top:       0,
		size:      size,
	}
}

func (s *Stack) IsFull() bool {
	return s.top == s.size

}

func (s *Stack) IsEmpty() bool {
	return s.top == 0
}

func (s *Stack) Push(e interface{}) bool {
	if s.IsFull() {
		return false
	}
	s.container[s.top] = e
	s.top++
	return true
}

func (s *Stack) Pop() (flag bool, ret interface{}) {
	if s.IsEmpty() {
		return false, ret
	}
	ret = s.container[s.top-1]
	s.top--
	return true, ret
}

func IsValid(s string) bool {
	stack := NewStack(100)
	// 遍历括号字符串
	for _, v := range s {
		if v == '(' {
			// 由于golang中的字符串默认是unicode编码，所以我们要做一个强制类型转换
			stack.Push(byte(v))
		}
		if v == ')' {
			// 如果flag不为true，说明栈已经到底了，可以直返回false
			if flag, top := stack.Pop(); flag && top == '(' {
				continue
			} else {
				return false
			}
		}
	}
	// 字符串遍历完后如果栈也空了，说明括号匹配

	// 如果栈不空，说明栈里还有多余的左括号
	return stack.IsEmpty()
}

func main() {

}
